package me.wangshier.leetcode.medium;

/**
 * 6. 小E的怪物挑战
 *
 * @Author: tongqianwen
 * @Date: 2025/3/4
 */
public class MonsterChallenge {
    public static int solution(int n, int H, int A, int[] h, int[] a) {
        //方法一：动态规划（Dynamic Programming）
        //步骤：
        //创建一个与原数组相同长度的数组dp，dp[i]表示以nums[i]结尾的最长递增子序列的长度。
        int[] dp = new int[n];
        //初始化所有dp[i]为1，因为每个单独的元素都可以构成一个长度为1的递增子序列。
        for (int i = 0; i < n; i++) {
            if(H>h[i] && A>a[i]){
                dp[i]=1;
            }else {
                dp[i]=0;
            }
        }
        //遍历数组，对于每个元素nums[i]，再次遍历其之前的所有元素nums[j]（j < i），
        // 如果nums[j] < nums[i]，则尝试更新dp[i] = max(dp[i], dp[j] + 1)。
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(h[i]>h[j] && a[i]>a[j] && A>a[i] && H>h[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        //在所有dp[i]中找到最大值，即为最长递增子序列的长度。
        int max = 0;
        for (int i = 0; i < n; i++) {
            if(dp[i]>max){
                max=dp[i];
            }
        }
        return max;
    }




    public static void main(String[] args) {
        System.out.println(solution(11, 14, 17, new int[]{14,16,2,16,3,10,9,6,3,6,10}, new int[]{14,9,11,10,7,1,12,2,10,17,17}) == 2);
        System.out.println(solution(3, 4, 5, new int[]{1, 2, 3}, new int[]{3, 2, 1}) == 1);
        System.out.println(solution(5, 10, 10, new int[]{6, 9, 12, 4, 7}, new int[]{8, 9, 10, 2, 5}) == 2);
        System.out.println(solution(4, 20, 25, new int[]{10, 15, 18, 22}, new int[]{12, 18, 20, 26}) == 3);
    }
}
